//
// Created by 高森森 on 2022/2/7.
//

#ifndef LEETCODE_SOLUTION24_H
#define LEETCODE_SOLUTION24_H


  struct ListNode {
      int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
  };

class Solution24 {
public:
    ListNode* insertionSortList(ListNode* head) {
        if(head== nullptr)
            return head;
        ListNode* preHead=new ListNode();
        preHead->next=head;
        ListNode *lastSorted=head;
        ListNode * cur=head->next;
        while(cur!= nullptr){
            if(lastSorted->val<=cur->val){
                lastSorted=cur;
            }else{
                ListNode * pre=preHead;
                while(pre->next->val<cur->val){
                    pre=pre->next;
                }
                lastSorted->next=cur->next;
                cur->next=pre->next;
                pre->next=cur;
            }
            cur=lastSorted->next;
        }
        return preHead->next;
    }
};

#endif //LEETCODE_SOLUTION24_H
